﻿using UnityEngine;
using UnityEngine.Rendering.Universal;

namespace Algorithm
{
    public abstract class Sort
    {
        public abstract  void SortArray(ref int[] numArray);

    }

    public class QuickSort : Sort
    {
        public override void SortArray(ref int[] numArray)
        {
            this.realSort(ref numArray, 0, numArray.Length -1);
            
        }

        private void realSort(ref int[] numArray, int left, int right)
        {
            if (left >= right)
            {
                return;
            }
            
            string PrintArray(int[] printArray)
            {
                var a = "";
                for (var i = 0; i < printArray.Length; i++)
                {
                    a += printArray[i] + "->";
                }
            
                return a;
            }

            Debug.Log("left:" + left + "   right:" + right + "=>"+PrintArray(numArray));

            var index = GetSortIndex(ref numArray, left, right);
            this.realSort(ref numArray,left , index -1);
            this.realSort(ref numArray,index + 1, right);
            
        }

        private int GetSortIndex(ref int[] numArray, int left, int right){
           

            var tempNum = numArray[left];
            while (left < right)
            {
                // 从右想向左找
                while (left < right && numArray[right] >= tempNum)
                {
                    right--;
                }

                if (left < right)
                {
                    numArray[left] = numArray[right];
                    left++;
                }
                // 从左往右找
                while (left < right && numArray[left] < tempNum)
                {
                    left++;
                }

                if (left < right)
                {
                    numArray[right] = numArray[left];
                    right--;
                }
            }
           

            numArray[left] = tempNum;
            return left;

        }
        
        
    }
}